diff --git a/sympy/simplify/cse_main.py b/sympy/simplify/cse_main.py
index cdbab4f608..1b65f060d7 100644
--- a/sympy/simplify/cse_main.py
+++ b/sympy/simplify/cse_main.py
@@ -409,7 +409,7 @@ def _find_opts(expr):
         if not isinstance(expr, (Basic, Unevaluated)):
             return
 
-        if expr.is_Atom or expr.is_Order:
+        if isinstance(expr, Basic) and (expr.is_Atom or expr.is_Order):
             return
 
         if iterable(expr):
@@ -422,7 +422,7 @@ def _find_opts(expr):
 
         list(map(_find_opts, expr.args))
 
-        if _coeff_isneg(expr):
+        if isinstance(expr, Basic) and _coeff_isneg(expr):
             neg_expr = -expr
             if not neg_expr.is_Atom:
                 opt_subs[expr] = Unevaluated(Mul, (S.NegativeOne, neg_expr))
@@ -437,7 +437,7 @@ def _find_opts(expr):
 
         elif isinstance(expr, (Pow, MatPow)):
             base, exp = expr.base, expr.exp
-            if _coeff_isneg(exp):
+            if isinstance(exp, Basic) and _coeff_isneg(exp):
                 opt_subs[expr] = Unevaluated(Pow, (Pow(base, -exp), -1))
 
     for e in exprs:
@@ -475,12 +475,17 @@ def tree_cse(exprs, symbols, opt_subs=None, order='canonical', ignore=()):
         The expressions to reduce.
     symbols : infinite iterator yielding unique Symbols
         The symbols used to label the common subexpressions which are pulled
-        out.
+        out. The ``numbered_symbols`` generator is useful. The default is a
+        stream of symbols of the form "x0", "x1", etc. This must be an
+        infinite iterator.
     opt_subs : dictionary of expression substitutions
         The expressions to be substituted before any CSE action is performed.
     order : string, 'none' or 'canonical'
-        The order by which Mul and Add arguments are processed. For large
-        expressions where speed is a concern, use the setting order='none'.
+        The order by which Mul and Add arguments are processed. If set to
+        'canonical', arguments will be canonically ordered. If set to 'none',
+        ordering will be faster but dependent on expressions hashes, thus
+        machine dependent and variable. For large expressions where speed is a
+        concern, use the setting order='none'.
     ignore : iterable of Symbols
         Substitutions containing any Symbol from ``ignore`` will be ignored.
     """
@@ -500,34 +505,34 @@ def _find_repeated(expr):
         if not isinstance(expr, (Basic, Unevaluated)):
             return
 
-        if isinstance(expr, Basic) and (expr.is_Atom or expr.is_Order):
-            if expr.is_Symbol:
-                excluded_symbols.add(expr)
-            return
+        if isinstance(expr, Basic):
+            if expr.is_Atom or expr.is_Order:
+                if expr.is_Symbol:
+                    excluded_symbols.add(expr)
+                return
 
-        if iterable(expr):
-            args = expr
-
-        else:
-            if expr in seen_subexp:
-                for ign in ignore:
-                    if ign in expr.free_symbols:
-                        break
-                else:
-                    to_eliminate.add(expr)
-                    return
+            if iterable(expr):
+                args = expr
+            else:
+                if expr in seen_subexp:
+                    for ign in ignore:
+                        if isinstance(expr, Basic) and ign in expr.free_symbols:
+                            break
+                    else:
+                        to_eliminate.add(expr)
+                        return
 
-            seen_subexp.add(expr)
+                seen_subexp.add(expr)
 
-            if expr in opt_subs:
-                expr = opt_subs[expr]
+                if expr in opt_subs:
+                    expr = opt_subs[expr]
 
-            args = expr.args
+                args = expr.args
 
-        list(map(_find_repeated, args))
+            list(map(_find_repeated, args))
 
     for e in exprs:
-        if isinstance(e, Basic):
+        if isinstance(e, (Basic, Unevaluated)):
             _find_repeated(e)
 
     ## Rebuild tree
@@ -546,16 +551,15 @@ def _rebuild(expr):
         if not expr.args:
             return expr
 
-        if iterable(expr):
-            new_args = [_rebuild(arg) for arg in expr]
+        if isinstance(expr, Unevaluated):
+            # Directly use the args attribute of Unevaluated objects
+            new_args = [_rebuild(arg) for arg in expr.args]
             return expr.func(*new_args)
-
-        if expr in subs:
-            return subs[expr]
-
-        orig_expr = expr
-        if expr in opt_subs:
-            expr = opt_subs[expr]
+        else:
+            # Existing logic for iterable expressions
+            if iterable(expr):
+                new_args = [_rebuild(arg) for arg in expr]
+                return expr.func(*new_args)
 
         # If enabled, parse Muls and Adds arguments by order to ensure
         # replacement order independent from hashes
@@ -585,13 +589,21 @@ def _rebuild(expr):
             except StopIteration:
                 raise ValueError("Symbols iterator ran out of symbols.")
 
-            if isinstance(orig_expr, MatrixExpr):
-                sym = MatrixSymbol(sym.name, orig_expr.rows,
-                    orig_expr.cols)
+            # Check if the original expression is a MatrixSymbol indexing operation
+            if isinstance(orig_expr, MatrixSymbol) and hasattr(orig_expr, 'indices'):
+                sym = MatrixSymbol(sym.name, orig_expr.rows, orig_expr.cols)
+                # Instead of directly substituting the symbol, substitute the indexed access
+                indexed_expr = orig_expr[orig_expr.indices]
+                subs[orig_expr] = indexed_expr
+                replacements.append((indexed_expr, new_expr))
+                return indexed_expr
+            else:
+                if isinstance(orig_expr, MatrixExpr):
+                    sym = MatrixSymbol(sym.name, orig_expr.rows, orig_expr.cols)
 
-            subs[orig_expr] = sym
-            replacements.append((sym, new_expr))
-            return sym
+                subs[orig_expr] = sym
+                replacements.append((sym, new_expr))
+                return sym
 
         else:
             return new_expr
